package 算法.leetcode.offer;

import 算法.leetcode.offer.base.TreeNode;

import java.util.Arrays;

/**
 * @author lchenglong
 * @date 2022/4/27
 */
public class Offer26 {

    public static void main(String[] args) {
        Offer26 instance = new Offer26();
        TreeNode A  = TreeNode.init(Arrays.asList(1,2,3,4));
        TreeNode B = TreeNode.init(Arrays.asList(3));
        boolean ans = instance.isSubStructure(A, B);
        System.out.println(ans);
    }
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // recur(A, B) 以A为根节点的子树
        // isSubStructure(A.left,B) , 判断树B是否是A的左子树的子结构
        // isSubStructure(A.right,B) , 判断树B是否是A的右子树的子结构
        return (A!=null&&B!=null)&&(dfs(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B));
    }

    public boolean dfs(TreeNode A,TreeNode B){
        // 当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true
        if (B == null)return true;
        // 当节点 A为空(此时B不为空)：说明已经越过树 A 叶子节点，即匹配失败
        // 当节点 A 和 B 的值不同：说明匹配失败
        if (A==null||A.val!=B.val)return false;
        return dfs(A.right,B.right) &&dfs(A.left,B.left);
    }
}
